{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from numpy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class treeNode():\n",
    "    def __int__(self  ,feat ,val ,right , left):\n",
    "        featureToSplitOn = feat\n",
    "        valueOfSplit = right\n",
    "        leftBranch = left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def loadDataSet(fileName):\n",
    "    dataMat  = []\n",
    "    fr = open(fileName)\n",
    "    for line in fr.readlines():\n",
    "        curLine = line.strip().split('\\t')\n",
    "        fltLine = list(map(float , curLine))\n",
    "        dataMat.append(fltLine)\n",
    "    return list(dataMat)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def binSplitDataSet(dataSet, feature, value):\n",
    "    mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:]\n",
    "    mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:]\n",
    "    return mat0,mat1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def regLeaf(dataSet):\n",
    "    return np.mean(dataSet[:,-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def regErr(dataSet):\n",
    "    return np.var(dataSet[:,-1]) * shape(dataSet)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def linearSolve(dataSet):   \n",
    "    m,n = shape(dataSet)\n",
    "    X = mat(ones((m,n))); Y = mat(ones((m,1)))\n",
    "    X[:,1:n] = dataSet[:,0:n-1]; Y = dataSet[:,-1]\n",
    "    xTx = X.T*X\n",
    "    if linalg.det(xTx) == 0.0:\n",
    "        raise NameError('This matrix is singular, cannot do inverse,\\n\\\n",
    "        try increasing the second value of ops')\n",
    "    ws = xTx.I * (X.T * Y)\n",
    "    return ws,X,Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def chooseBestSplit(dataSet,leafType=regLeaf,errType=regErr,ops=(1,4)):\n",
    "    tolS = ops[0]\n",
    "    tolN = ops[1]\n",
    "    if len(set(dataSet[:,-1].T.tolist()[0])) == 1:\n",
    "        return None ,leafType(dataSet)\n",
    "    m , n = dataSet.shape\n",
    "    S = errType(dataSet)\n",
    "    bestS = inf\n",
    "    bestIndex = 0\n",
    "    bestValue = 0\n",
    "    for featIndex in range(n-1):\n",
    "        for splitVal in set(list(dataSet[:,featIndex].A.reshape(-1))):\n",
    "            mat0 , mat1  = binSplitDataSet(dataSet,featIndex,splitVal)\n",
    "            if (mat0.shape[0] < tolN) or (mat1.shape[0] < tolN):continue\n",
    "            news = errType(mat0) + errType(mat1)\n",
    "            if news < bestS:\n",
    "                bestIndex = featIndex\n",
    "                bestValue = splitVal\n",
    "                bestS = news\n",
    "    if (S - bestS ) < tolS:\n",
    "        return None , leafType(dataSet)\n",
    "    mat0 ,mat1 = binSplitDataSet(dataSet,bestIndex,bestValue)\n",
    "    if (mat0.shape[0] < tolN) or (mat1.shape[0] < tolN):\n",
    "        return None , leafType(dataSet)\n",
    "    return bestIndex , bestValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def createTree(dataSet,leafType=regLeaf,errType=regErr,ops=(1,4)):\n",
    "    feat , val = chooseBestSplit(dataSet,leafType,errType,ops)\n",
    "    if feat == None : return val\n",
    "    retTree = {}\n",
    "    retTree['spInd'] = feat\n",
    "    retTree['spVal'] = val\n",
    "    lSet , rSet = binSplitDataSet(dataSet,feat,val)\n",
    "    retTree['left'] = createTree(lSet,leafType,errType,ops)\n",
    "    retTree['right'] = createTree(rSet,leafType,errType,ops)\n",
    "    return retTree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 0,  1,  2],\n",
       "        [ 3,  4,  5],\n",
       "        [ 6,  7,  8],\n",
       "        [ 9, 10, 11],\n",
       "        [12, 13, 14],\n",
       "        [15, 16, 17]])"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "testMat = np.mat(np.arange(18).reshape(6,3))\n",
    "testMat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "mat0 , mat1  = binSplitDataSet(testMat,1,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[ 3,  4,  5],\n",
       "        [ 6,  7,  8],\n",
       "        [ 9, 10, 11],\n",
       "        [12, 13, 14],\n",
       "        [15, 16, 17]])"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[0, 1, 2]])"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mat1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': 14.0, 'right': 5.0, 'spInd': 0, 'spVal': 6}"
      ]
     },
     "execution_count": 104,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "createTree(testMat,ops=(1,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "myData  = loadDataSet('ex00.txt')\n",
    "myMat = np.mat(myData)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': 1.0180967672413792,\n",
       " 'right': -0.04465028571428572,\n",
       " 'spInd': 0,\n",
       " 'spVal': 0.48813}"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "createTree(myMat,ops=(1,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': {'left': {'left': 3.9871632,\n",
       "   'right': 2.9836209534883724,\n",
       "   'spInd': 1,\n",
       "   'spVal': 0.797583},\n",
       "  'right': 1.980035071428571,\n",
       "  'spInd': 1,\n",
       "  'spVal': 0.582002},\n",
       " 'right': {'left': 1.0289583666666666,\n",
       "  'right': -0.023838155555555553,\n",
       "  'spInd': 1,\n",
       "  'spVal': 0.197834},\n",
       " 'spInd': 1,\n",
       " 'spVal': 0.39435}"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myData1 = loadDataSet('ex0.txt')\n",
    "myMat1 = np.mat(myData1)\n",
    "createTree(myMat1 ,ops=(1,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': {'left': {'left': {'left': 105.24862350000001,\n",
       "    'right': 112.42895575000001,\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.958512},\n",
       "   'right': {'left': {'left': {'left': {'left': 87.3103875,\n",
       "       'right': {'left': {'left': 96.452867,\n",
       "         'right': {'left': 104.825409,\n",
       "          'right': {'left': 95.181793,\n",
       "           'right': 102.25234449999999,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.872883},\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.892999},\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.910975},\n",
       "        'right': 95.27584316666666,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.85497},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.944221},\n",
       "      'right': {'left': 81.110152,\n",
       "       'right': 88.78449880000001,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.811602},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.833026},\n",
       "     'right': 102.35780185714285,\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.790312},\n",
       "    'right': 78.08564325,\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.759504},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.952833},\n",
       "  'right': {'left': {'left': {'left': 114.554706,\n",
       "     'right': {'left': 104.82495374999999,\n",
       "      'right': 108.92921799999999,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.698472},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.706961},\n",
       "    'right': 114.1516242857143,\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.666452},\n",
       "   'right': {'left': 93.67344971428572,\n",
       "    'right': {'left': 123.2101316,\n",
       "     'right': {'left': 97.20018024999999,\n",
       "      'right': {'left': {'left': 109.38961049999999,\n",
       "        'right': 110.979946,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.543843},\n",
       "       'right': 101.73699325000001,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.51915},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.553797},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.582311},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.613004},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.640515},\n",
       "  'spInd': 0,\n",
       "  'spVal': 0.729397},\n",
       " 'right': {'left': {'left': 12.50675925,\n",
       "   'right': 3.4331330000000007,\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.467383},\n",
       "  'right': {'left': {'left': {'left': -12.558604833333334,\n",
       "     'right': {'left': 14.38417875,\n",
       "      'right': {'left': -0.8923554999999995,\n",
       "       'right': 3.6584772500000016,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.385021},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.412516},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.437652},\n",
       "    'right': {'left': {'left': -15.08511175,\n",
       "      'right': -22.693879600000002,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.350725},\n",
       "     'right': {'left': 15.05929075,\n",
       "      'right': {'left': -19.9941552,\n",
       "       'right': {'left': {'left': {'left': {'left': {'left': 0.40377471428571476,\n",
       "            'right': -13.070501,\n",
       "            'spInd': 0,\n",
       "            'spVal': 0.25807},\n",
       "           'right': 6.770429,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.228473},\n",
       "          'right': -11.822278500000001,\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.217214},\n",
       "         'right': 3.4496025,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.202161},\n",
       "        'right': {'left': -12.1079725,\n",
       "         'right': -6.247900000000001,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.156067},\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.166765},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.297107},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.324274},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.335182},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.373501},\n",
       "   'right': {'left': 6.509843285714284,\n",
       "    'right': {'left': -2.544392714285715,\n",
       "     'right': 4.091626,\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.044737},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.084661},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.126833},\n",
       "  'spInd': 0,\n",
       "  'spVal': 0.457563},\n",
       " 'spInd': 0,\n",
       " 'spVal': 0.499171}"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myData2 = loadDataSet('ex2.txt')\n",
    "myMat2 = np.mat(myData2)\n",
    "createTree(myMat2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': 101.35815937735848,\n",
       " 'right': -2.637719329787234,\n",
       " 'spInd': 0,\n",
       " 'spVal': 0.499171}"
      ]
     },
     "execution_count": 109,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "createTree(myMat2,ops=(10000,4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def isTree(obj):\n",
    "    return (type(obj).__name__=='dict')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def getMean(tree):\n",
    "    if isTree(tree['right']): tree['right'] = getMean(tree['right'])\n",
    "    if isTree(tree['left']): tree['left'] = getMean(tree['left'])\n",
    "    return (tree['left']+tree['right'])/2.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def prune(tree, testData):\n",
    "    if shape(testData)[0] == 0: return getMean(tree)\n",
    "    if (isTree(tree['right']) or isTree(tree['left'])):\n",
    "        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])\n",
    "    if isTree(tree['left']): tree['left'] = prune(tree['left'], lSet)\n",
    "    if isTree(tree['right']): tree['right'] =  prune(tree['right'], rSet)\n",
    "    if not isTree(tree['left']) and not isTree(tree['right']):\n",
    "        lSet, rSet = binSplitDataSet(testData, tree['spInd'], tree['spVal'])\n",
    "        errorNoMerge = sum(power(lSet[:,-1] - tree['left'],2)) +\\\n",
    "            sum(power(rSet[:,-1] - tree['right'],2))\n",
    "        treeMean = (tree['left']+tree['right'])/2.0\n",
    "        errorMerge = sum(power(testData[:,-1] - treeMean,2))\n",
    "        if errorMerge < errorNoMerge: \n",
    "            print (\"merging\")\n",
    "            return treeMean\n",
    "        else: return tree\n",
    "    else: return tree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "myTree = createTree(myMat2,ops=(0,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n",
      "merging\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'left': {'left': {'left': {'left': {'left': {'left': {'left': {'left': 11.863062,\n",
       "        'right': 11.782002,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.996587},\n",
       "       'right': 11.68401,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.988631},\n",
       "      'right': 11.928754,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.987041},\n",
       "     'right': {'left': {'left': 11.716573,\n",
       "       'right': 11.683243,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.973524},\n",
       "      'right': 11.521595,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.964229},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.984061},\n",
       "    'right': {'left': 11.2516095,\n",
       "     'right': {'left': {'left': {'left': {'left': 10.833902,\n",
       "         'right': 10.8934675,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.915586},\n",
       "        'right': 10.775188,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.906907},\n",
       "       'right': 10.978834,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.903683},\n",
       "      'right': 10.7494505,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.900938},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.915906},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.946702},\n",
       "   'right': {'left': {'left': {'left': {'left': 10.420003,\n",
       "       'right': 10.4702025,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.883872},\n",
       "      'right': 10.54077975,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.879259},\n",
       "     'right': {'left': {'left': 10.246888,\n",
       "       'right': 10.367476,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.859396},\n",
       "      'right': 10.17218,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.838332},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.861891},\n",
       "    'right': {'left': {'left': {'left': {'left': {'left': 9.932258000000001,\n",
       "         'right': 9.856432,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.829402},\n",
       "        'right': 9.9887065,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.824724},\n",
       "       'right': {'left': 9.743861,\n",
       "        'right': 9.93614,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.821941},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.82346},\n",
       "      'right': {'left': 9.648134500000001,\n",
       "       'right': 9.6908625,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.804148},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.806349},\n",
       "     'right': {'left': {'left': 9.423494250000001,\n",
       "       'right': 9.4865045,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.785298},\n",
       "      'right': 9.317914,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.782509},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.796083},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.831633},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.889088},\n",
       "  'right': {'left': {'left': {'left': {'left': 9.199101,\n",
       "      'right': {'left': 8.885337,\n",
       "       'right': 9.176722,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.756591},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.758564},\n",
       "     'right': {'left': {'left': 8.966676,\n",
       "       'right': {'left': 8.942278,\n",
       "        'right': 8.949407,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.747221},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.747582},\n",
       "      'right': 8.84563125,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.739494},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.747609},\n",
       "    'right': {'left': {'left': {'left': {'left': 8.526944,\n",
       "        'right': 8.663569,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.721517},\n",
       "       'right': {'left': 8.504348,\n",
       "        'right': 8.476718,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.70697},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.717509},\n",
       "      'right': {'left': 8.432886,\n",
       "       'right': {'left': 8.298454,\n",
       "        'right': {'left': 8.417306,\n",
       "         'right': 8.307487,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.696399},\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.699852},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.702748},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.705127},\n",
       "     'right': {'left': 8.209058,\n",
       "      'right': {'left': 8.067282,\n",
       "       'right': 8.034081,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.66897},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.675922},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.695091},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.7237},\n",
       "   'right': {'left': {'left': {'left': {'left': {'left': 7.948868,\n",
       "        'right': 7.880333,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.658125},\n",
       "       'right': 8.028558,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.65498},\n",
       "      'right': {'left': 7.8070125,\n",
       "       'right': 7.790882,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.645825},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.65464},\n",
       "     'right': {'left': {'left': 7.632114,\n",
       "       'right': 7.556742,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.628951},\n",
       "      'right': 7.703312,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.619535},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.640341},\n",
       "    'right': {'left': {'left': {'left': 7.312725,\n",
       "       'right': 7.272665,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.609194},\n",
       "      'right': {'left': 7.188805,\n",
       "       'right': {'left': 7.112627,\n",
       "        'right': 7.146694,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.597514},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.597578},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.601418},\n",
       "     'right': {'left': {'left': {'left': 6.893128,\n",
       "        'right': 7.029661,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.586694},\n",
       "       'right': 6.903597,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.583567},\n",
       "      'right': 7.040672,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.574813},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.588088},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.618869},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.667199},\n",
       "  'spInd': 0,\n",
       "  'spVal': 0.763717},\n",
       " 'right': {'left': {'left': {'left': {'left': {'left': 6.764615,\n",
       "      'right': 6.71521,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.551771},\n",
       "     'right': {'left': 6.483512,\n",
       "      'right': {'left': {'left': 6.39394,\n",
       "        'right': 6.377132,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.534076},\n",
       "       'right': 6.305005,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.531069},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.538982},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.546308},\n",
       "    'right': {'left': {'left': {'left': 6.067444,\n",
       "       'right': {'left': 6.26606,\n",
       "        'right': {'left': 6.202835,\n",
       "         'right': 6.166836,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.512739},\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.519998},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.524366},\n",
       "      'right': {'left': 6.0366775,\n",
       "       'right': {'left': 6.1152535,\n",
       "        'right': 6.02206,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.48732},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.502217},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.510342},\n",
       "     'right': {'left': {'left': {'left': 5.681631,\n",
       "        'right': 5.871813,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.473786},\n",
       "       'right': 5.532255,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.466781},\n",
       "      'right': 5.833439,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.466011},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.478773},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.524701},\n",
       "   'right': {'left': 5.3395005,\n",
       "    'right': {'left': 5.032168,\n",
       "     'right': {'left': 4.92732775,\n",
       "      'right': {'left': {'left': 4.85638,\n",
       "        'right': 4.893403,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.404396},\n",
       "       'right': 4.934647,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.399447},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.411291},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.417559},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.429009},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.453779},\n",
       "  'right': {'left': {'left': {'left': {'left': {'left': 4.61139,\n",
       "       'right': 4.773104,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.396533},\n",
       "      'right': 4.42697,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.385001},\n",
       "     'right': {'left': 4.830712,\n",
       "      'right': 4.649362,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.384638},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.384794},\n",
       "    'right': {'left': {'left': 4.3903680000000005,\n",
       "      'right': {'left': 4.325355,\n",
       "       'right': 4.263666,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.355214},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.357325},\n",
       "     'right': 4.10976825,\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.348564},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.3749},\n",
       "   'right': {'left': {'left': {'left': 3.971613,\n",
       "      'right': 3.8775605,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.336599},\n",
       "     'right': {'left': {'left': {'left': {'left': 3.7507745000000003,\n",
       "         'right': {'left': 3.681148,\n",
       "          'right': 3.671373,\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.304401},\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.30609},\n",
       "        'right': 3.818961,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.285477},\n",
       "       'right': 3.609353,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.28432},\n",
       "      'right': {'left': 3.88173975,\n",
       "       'right': {'left': {'left': {'left': {'left': 3.75722775,\n",
       "           'right': 3.679117,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.25067},\n",
       "          'right': {'left': 3.75852,\n",
       "           'right': 3.795962,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.233675},\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.244888},\n",
       "         'right': {'left': 3.546938,\n",
       "          'right': {'left': 3.713645,\n",
       "           'right': 3.740024,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.212118},\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.220512},\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.226271},\n",
       "        'right': {'left': 3.9474935,\n",
       "         'right': {'left': {'left': {'left': 3.667477,\n",
       "            'right': 3.638493,\n",
       "            'spInd': 0,\n",
       "            'spVal': 0.190201},\n",
       "           'right': 3.711018,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.188907},\n",
       "          'right': {'left': 3.97642,\n",
       "           'right': {'left': 3.778095,\n",
       "            'right': 3.678579,\n",
       "            'spInd': 0,\n",
       "            'spVal': 0.181268},\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.182523},\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.188617},\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.192256},\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.196731},\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.264587},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.2842},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.313967},\n",
       "    'right': {'left': {'left': {'left': {'left': 3.5591299999999997,\n",
       "        'right': {'left': 3.672945,\n",
       "         'right': 3.552314,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.150262},\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.163007},\n",
       "       'right': 3.743681,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.142295},\n",
       "      'right': {'left': {'left': {'left': 3.5772767500000002,\n",
       "         'right': 3.55558725,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.117348},\n",
       "        'right': 3.470829,\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.07067},\n",
       "       'right': 3.6577555000000004,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.066532},\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.141105},\n",
       "     'right': {'left': {'left': {'left': {'left': {'left': {'left': 3.484805,\n",
       "           'right': 3.431537,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.059849},\n",
       "          'right': 3.575105,\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.050129},\n",
       "         'right': {'left': {'left': 3.429691,\n",
       "           'right': 3.356861,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.039657},\n",
       "          'right': {'left': 3.515624,\n",
       "           'right': 3.470285,\n",
       "           'spInd': 0,\n",
       "           'spVal': 0.019095},\n",
       "          'spInd': 0,\n",
       "          'spVal': 0.025501},\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.039768},\n",
       "        'right': {'left': 3.5384495,\n",
       "         'right': 3.565835,\n",
       "         'spInd': 0,\n",
       "         'spVal': 0.010767},\n",
       "        'spInd': 0,\n",
       "        'spVal': 0.014611},\n",
       "       'right': 3.33315,\n",
       "       'spInd': 0,\n",
       "       'spVal': 0.005144},\n",
       "      'right': 3.587139,\n",
       "      'spInd': 0,\n",
       "      'spVal': 0.003174},\n",
       "     'spInd': 0,\n",
       "     'spVal': 0.059988},\n",
       "    'spInd': 0,\n",
       "    'spVal': 0.176767},\n",
       "   'spInd': 0,\n",
       "   'spVal': 0.337828},\n",
       "  'spInd': 0,\n",
       "  'spVal': 0.396583},\n",
       " 'spInd': 0,\n",
       " 'spVal': 0.57}"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myDataTest = loadDataSet('ex2test.txt')\n",
    "myMat2Test = np.mat(myDataTest)\n",
    "prune(myTree , myMat2Test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def linearSolve(dataSet):\n",
    "    m , n = shape(dataSet)\n",
    "    X  = np.mat(np.ones((m,n)))\n",
    "    Y = np.mat(np.ones((m,1)))\n",
    "    X[:,1:n] = dataSet[:,0:n-1]\n",
    "    Y = dataSet[:,-1]\n",
    "    xTx = X.T * X\n",
    "    if np.linalg.det(xTx) == 0.0:\n",
    "        raise NameError ('this matrix is singular ,cannot do inverse ,\\n\\\n",
    "            try increasing the second value of ops')\n",
    "    ws = xTx.I* (X.T * Y)\n",
    "    return ws,X , Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def modelLeaf(dataSet):\n",
    "    ws , X ,Y = linearSolve(dataSet)\n",
    "    return ws"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def modelErr(dataSet):\n",
    "    ws ,X , Y = linearSolve(dataSet)\n",
    "    yHat = X * ws\n",
    "    return np.sum(np.power(Y - yHat , 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'left': matrix([[1.69855694e-03],\n",
       "         [1.19647739e+01]]), 'right': matrix([[3.46877936],\n",
       "         [1.18521743]]), 'spInd': 0, 'spVal': 0.285477}"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myMat2 = np.mat(loadDataSet('exp2.txt')) \n",
    "createTree(myMat2,modelLeaf,modelErr,(1,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def regTreeEval(model, inDat):\n",
    "    return float(model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def modelTreeEval(model, inDat):\n",
    "    n = shape(inDat)[1]\n",
    "    X = mat(ones((1,n+1)))\n",
    "    X[:,1:n+1]=inDat\n",
    "    return float(X*model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def treeForeCast(tree, inData, modelEval=regTreeEval):\n",
    "    if not isTree(tree): return modelEval(tree, inData)\n",
    "    if inData[tree['spInd']] > tree['spVal']:\n",
    "        if isTree(tree['left']): return treeForeCast(tree['left'], inData, modelEval)\n",
    "        else: return modelEval(tree['left'], inData)\n",
    "    else:\n",
    "        if isTree(tree['right']): return treeForeCast(tree['right'], inData, modelEval)\n",
    "        else: return modelEval(tree['right'], inData)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def createForeCast(tree, testData, modelEval=regTreeEval):\n",
    "    m=len(testData)\n",
    "    yHat = mat(zeros((m,1)))\n",
    "    for i in range(m):\n",
    "        yHat[i,0] = treeForeCast(tree, mat(testData[i]), modelEval)\n",
    "    return yHat"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 创建一棵回归树11111"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "trainMat = np.mat(loadDataSet('bikeSpeedVsIq_train.txt'))\n",
    "testMat = np.mat(loadDataSet('bikeSpeedVsIq_test.txt'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9640852318222141"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree = createTree(trainMat ,ops=(1,20))\n",
    "yHat = createForeCast(myTree , testMat[:,0])\n",
    "np.corrcoef(yHat, testMat[:,1],rowvar=0)[0,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 创建一棵模型树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9760412191380621"
      ]
     },
     "execution_count": 181,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "myTree = createTree(trainMat,modelLeaf,modelErr,(1,20))\n",
    "yHat = createForeCast(myTree,testMat[:,0],modelTreeEval)\n",
    "np.corrcoef(yHat,testMat[:,1],rowvar=0)[0,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 创建标准线性回归·"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ws , X ,Y = linearSolve(trainMat)\n",
    "for i in range(shape(testMat)[0]):\n",
    "    yHat[i] = testMat[i,0] * ws[1,0] + ws[0,0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9434684235674758"
      ]
     },
     "execution_count": 154,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.corrcoef(yHat, testMat[:,1],rowvar=0)[0,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
